package com.dmall.graph.euler;

import com.dmall.graph.Graph;
import com.dmall.graph.dfs.app.CC;

import java.util.*;

/**
 * 使用递归的方式找欧拉回路
 * @author xiao1.wang
 * @date 2022-07-05 14:24:41
 */
public class EulerLoopRecursion {

    private Graph G;
    private List<Integer> res;
    private Set<String> visited;

    public EulerLoopRecursion(Graph G) {
        this.G = G;
    }

    public boolean hasEulerLoop() {
        CC cc = new CC(G);
        if (cc.count() > 1) {
            return false;
        }
        for (int v = 0; v < G.V(); v++) {
            if (G.degree(v) % 2 == 1) {
                return false;
            }
        }
        return true;
    }

    public List<Integer> result() {
        res = new ArrayList<>();
        visited = new HashSet<>();
        if (!hasEulerLoop()) {
            return res;
        }
        Graph g = (Graph) G.clone();
        recursion(0, g);
        return res;
    }

    private void recursion(int v, Graph g) {
        for (int w : g.adj(v)) {
            String key1 = v + "-" + w;
            String key2 = w + "-" + v;
            if (!visited.contains(key1) && !visited.contains(key2)) {
                visited.add(key1);
                visited.add(key2);
                recursion(w, g);
            }
        }
        res.add(v);
    }

    public static void main(String[] args) {
        String filename = EulerLoopRecursion.class.getClassLoader().getResource("g.txt").getPath();
        Graph g = new Graph(filename);
        EulerLoopRecursion el = new EulerLoopRecursion(g);
        System.out.println(el.result());

        String filename2 = EulerLoopRecursion.class.getClassLoader().getResource("g2.txt").getPath();
        Graph g2 = new Graph(filename2);
        EulerLoopRecursion el2 = new EulerLoopRecursion(g2);
        System.out.println(el2.result());
    }
}
